package org.example.code.test2024.nine_mouth;

import java.util.*;

public class test0911 {
    public String decodeString(String s) {
        if(s.isEmpty()){
            return s;
        }
        Stack<Integer> integerStack = new Stack<>();
        Stack<StringBuilder> stringStack = new Stack<>();
        char[] chars = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        int k = 0;
        for (char aChar : chars) {
            if (aChar == '[') {
                integerStack.push(k);
                stringStack.push(sb);
                sb = new StringBuilder();
                k = 0;
            } else if (aChar == ']') {
                int temp = integerStack.pop();
                StringBuilder str = stringStack.pop();
                for (int j = 0; j < temp; j++) {
                    str.append(sb);
                }
                sb = str;
            } else if (Character.isDigit(aChar)) {
                k = k * 10 + (aChar - '0');
            } else {
                sb.append(aChar);
            }
        }
        return sb.toString();
    }

    public int[] dailyTemperatures(int[] temperatures) {
        int[] result = new int[temperatures.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < temperatures.length; i++) {
            if(stack.isEmpty()){
                stack.push(i);
                continue;
            }
            while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]) {
                result[stack.peek()] = i - stack.peek();
                stack.pop();
            }
            stack.push(i);
        }
        while(!stack.empty()){
            result[stack.pop()]=0;
        }
        return result;
    }

    public int largestRectangleArea(int[] heights) {
        if(heights == null || heights.length == 0){
            return 0;
        }
        if(heights.length == 1){
            return heights[0];
        }
        Stack<Integer> stack = new Stack<>();
        int max = 0;
        for(int i=0;i<=heights.length;i++){
            int h = (i == heights.length)?0:heights[i];
            while(!stack.isEmpty()&&heights[stack.peek()]>h){
                int height = heights[stack.pop()];
                int width = stack.isEmpty()?i:i - stack.peek()-1;
                max = Math.max(max,height*width);
            }
            stack.push(i);
        }
        return max;
    }

    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int num : nums) {
            if (queue.size() < k) {
                queue.offer(num);
            } else if(queue.peek() < num) {
                queue.poll();
                queue.offer(num);
            }
        }
        return queue.peek();
    }

    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int num : nums){
            if(map.containsKey(num)){
                map.put(num,map.get(num)+1);
            }else {
                map.put(num,1);
            }
        }
        PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(k,
                Comparator.comparingInt(Map.Entry::getValue));
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if(minHeap.size() < k){
                minHeap.add(entry);
            }else if(minHeap.peek().getValue() < entry.getValue()){
                minHeap.poll();
                minHeap.add(entry);
            }
        }
        int[]  result = new int[k];
        for(int i=0;i<k;i++){
            result[i] = minHeap.poll().getKey();
        }
        return result;
    }

    public static void main(String[] args) {
        test0911 test0911 = new test0911();
        int[] nums = {4,1,-1,2,-1,2,3};
        System.out.println(Arrays.toString(test0911.topKFrequent(nums, 2)));
    }
}
//1,1,4,2,1,1,0,0